package philbot;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;



/**
 * @author philip 
 * * This class does the core of the evaluation work. 
 * All the game tree evaluation algorithms happen in this class.
 */
public class PhilBotCore {
	/**
	 * Possible search algorithms
	 * @author philip
	 *
	 */
	public static enum SearchAlg{
		NEGAMAX, ABPRUNING, MEMORYAB
	}
	/**
	 * Possible search types
	 * @author philip
	 *
	 */
	public static enum SearchMode{
		SIMPLE, ID 
	}
	/**
	 * Possible search tree node types
	 * @author philip
	 *
	 */
	private static enum NodeType{
		PV, CUT, ALL
	}
	/**
	 * How many times has the transposition table had what we were looking for
	 */
	public int hitCount;
	/**
	 * How many nodes have we searched
	 */
	public int nodeCount;
	/**
	 * What is the maximum number of nodes to search
	 */
	private int nodeCutoff;
	private boolean reachedCutoff;
	
	public long burnCount;
	/**
	 * The transposition table we use
	 */
	public TransTable table;
	/**
	 * The PV table we use--stores best responses, so is useful for getting the next move in a game
	 */
	public PVTable pvtable;
	
	/**
	 * PhilBotCore
	 * @param table A transposition table used by the memory enhanced versions of the search.  It may be useful to use a single table for multiple searches
	 */
	public PhilBotCore(TransTable table){
		this.table = table;
		this.pvtable = new PVTable();
		this.hitCount = this.nodeCount = 0;
		this.burnCount = 0;
		this.nodeCutoff = Integer.MAX_VALUE;
	} 
	
	/**
	 * Negamax
	 * A pure negamax search.  Negamax is identical to Minimax.
	 * @param depth the maximum depth to look to.  Note, this value may not be reached if the Core reaches a number of nodes cutoff
	 * @param position the position to evaluate
	 * @param saveDepth --for all nodes searched where depth is greater than saveDepth, the search will save the best response in the PV table
	 * @return value returned by the search.
	 */
	public int negaMax(int depth, AbstractPosition position, Evaluator eval, int saveDepth){
		nodeCount++;
		if(nodeCount >= nodeCutoff){
			reachedCutoff = true;
			return 0;
		}
		int evaled = position.eval(eval);
		//should break if this is a victory
		if(depth < 1){
			return evaled;
		}
		List<AbstractPosition> nextPos = position.getChildren();
		AbstractPosition refutation = null;
		int best = Integer.MIN_VALUE;
		for(AbstractPosition p: nextPos){
			int trial = -this.negaMax(depth-1, p, eval, saveDepth);
			if (trial > best){
				best = trial;
				refutation = p;
			}
		}
		if(depth > saveDepth){
			pvtable.setPV(depth, position, refutation);
		}
		return best;
	}
	/**
	 * Pure Alpha Beta search
	 * This search does not utilize move ordering, because no good ordering values are saved along the way
	 * @param depth the maximum depth to look to.  Note, this value may not be reached if the Core reaches a number of nodes cutoff
	 * @param position the position to evaluate
	 * @param alpha the alpha bound
	 * @param beta the beta bound
	 * @param saveDepth --for all nodes searched where depth is greater than saveDepth, the search will save the best response in the PV table
	 * @return value returned by the search.
	 */
	public int alphaBeta(int depth, AbstractPosition position, int alpha, int beta, Evaluator eval, int saveDepth){
		nodeCount++;
		if(nodeCount >= nodeCutoff){
			reachedCutoff = true;
			return 0;
		}
		int evaled = position.eval(eval);
		if((depth < 1)||position.isVictory()){
			return evaled;
		}
		List<AbstractPosition> nextPos = position.getChildren();
		AbstractPosition best = null;
		for(AbstractPosition p: nextPos){
			int trial = -alphaBeta(depth -1, p, -beta, -alpha, eval, saveDepth);
			if (trial > alpha){
				alpha = trial;
				best = p;
			}
			if (alpha >= beta){
				break;
			}
		}
		if(depth > saveDepth){
			this.pvtable.setPV(depth, position,best);
		}
		return alpha;
	}
	/*
	public int iterativeDeepen(int depth, AbstractPosition position, int alpha, int beta){
		for(int i = 0; i < depth; i++){
			this.meAlphaBeta(i, position, alpha, beta, i-2);
		}
		return this.meAlphaBeta(depth, position, alpha, beta,depth-2);
	}
	*/
	/**
	 * Memory Enhanced Alpha Beta Search
	 * @param depth the maximum depth to look to.  Note, this value may not be reached if the Core reaches a number of nodes cutoff
	 * @param position the position to evaluate
	 * @param alpha the alpha bound
	 * @param beta the beta bound
	 * @param saveDepth --for all nodes searched where depth is greater than saveDepth, the search will save the best response in the PV table
	 * @return value returned by the search.
	 */
	public int meAlphaBeta(int depth, AbstractPosition position, int alpha, int beta, Evaluator eval, int saveDepth){
		nodeCount++;
		if(nodeCount >= nodeCutoff){
			reachedCutoff = true;
			return 0;
		}
		//check if victory
		if((depth < 1)||position.isVictory()){
			return position.eval(eval);
		}
		//check the hash
		Integer exact = table.getExact(position, depth);
		if(exact != null){
			hitCount++;
			return exact.intValue();
		}
		//alpha = alpha... that is we are at a lower bound
		NodeType bound = NodeType.ALL;
		List<AbstractPosition> nextPos = position.getChildren();
		AbstractPosition best = null;
		//TODO move ordering
		nodeCount++;
		inOrder(nextPos,eval);
		int i = 0;
		int j = 0;
		for(AbstractPosition p: nextPos){
			i++;
			int trial = -this.meAlphaBeta(depth -1, p, -beta, -alpha,eval,saveDepth);
			if (trial > alpha){
				alpha = trial;
				bound = NodeType.PV;
				best = p;
				j = i;
			}
			//prune!
			if (alpha >= beta){
				bound = NodeType.CUT;
				break;
			}
		}
		if(bound == NodeType.PV)
			table.setExact(position, depth, alpha);
		if(depth > saveDepth){
			pvtable.setPV(depth, position, best);
		}
		burnCount += j;
		return alpha;
	}
	
	
	/**
	 * ComparePos is the comparator used for move ordering.  
	 */
	private class ComparePos implements Comparator<AbstractPosition>{
		Evaluator eval;
		ComparePos(Evaluator eval){
			this.eval = eval;
		}
		@Override
		public int compare(AbstractPosition arg0, AbstractPosition arg1) {
			Integer v1 = table.getExact(arg0, 0);
			Integer v2 = table.getExact(arg1, 0);
			if(v1 == null){
				v1 = arg0.eval(eval);
			}else{
				hitCount++;
			}
			if(v2 == null)
				v2 = arg1.eval(eval);
			else{
				hitCount++;
			}
			int cv = 0; // (v2.compareTo(v1));
			if(cv == 0){
				if(arg0.createdByJump()){
					if(arg1.createdByJump())
						cv = 0;
					else
						cv = -1;
				}if(arg1.createdByJump()){
					cv = 1;
				}
			}
			//i am not sure about this line
			return cv;
		}
		
	}
	/**
	 * inOrder
	 * @param l a list of positions to be sorted. If available the sort will use the values stored in the transposition table of the enclosing core
	 * @param eval the evaluator used for sorting if no value for a position is found in the transposition table
	 */
	public void inOrder(List<AbstractPosition> l, Evaluator eval){
		Collections.sort(l, new ComparePos(eval));
	}
	
	/**
	 * innerSearch 
	 * @param alg the search algorithm to use
	 * @param position the starting position
	 * @param depth the maximum depth of the search tree
	 * @param alpha
	 * @param beta
	 * @param eval the evaluator to use
	 * @return the value returned by the sear
	 */
	private int innerSearch(SearchAlg alg, AbstractPosition position, int depth, int alpha, int beta, Evaluator eval){
		switch(alg){
			case NEGAMAX:
				return this.negaMax(depth, position, eval,depth-2);
			case ABPRUNING:
				return this.alphaBeta(depth, position, alpha, beta, eval,depth-2);
			case MEMORYAB:
				return this.meAlphaBeta(depth, position, alpha, beta, eval, depth-2);
		}
		return 0;
	}
	
	/**
	 * search
	 * A generalized method for carrying out different search strategies
	 * @param mode the mode of the search @see PhilBotCore.SearchMode
	 * @param alg the search algorithm to use @see PhilBotCore.SearchAlg
	 * @param position the starting position
	 * @param nodeCutoff the maximum number of nodes to investigate
	 * @param maxDepth the maximum depth of the search
	 * @param asWindow the size of the aspiration search window --not currently supported
	 * @param eval the evaluator to use in the search
	 * @return the value returned by the search.  The search will also save an optimal response for this position in the pvtable
	 */
	public int search(SearchMode mode, SearchAlg alg, AbstractPosition position, int nodeCutoff, int maxDepth, int asWindow, Evaluator eval){
		this.nodeCutoff = nodeCutoff;
		this.nodeCount = 0;
		this.reachedCutoff = false;
		switch(mode){
			case SIMPLE:
				return this.innerSearch(alg, position, maxDepth, Integer.MIN_VALUE, Integer.MAX_VALUE, eval);
			case ID:
				int b = 0;
				//need to handle small number of moves without stack overflowing
				for(int i = 1;i<=maxDepth&&(!reachedCutoff);i++){
					int t = this.innerSearch(alg, position, i, Integer.MIN_VALUE, Integer.MAX_VALUE, eval);
					if(!reachedCutoff)
						b = t;
					else{
						//System.out.println(i);
					}
				}
				return b;
		}
		return 0;
	}
}
